`
https://leetcode.cn/problems/all-possible-full-binary-trees/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var allPossibleFBT = function (n) {
  // 真二叉树的节点数不可能是偶数
  if (n % 2 === 0) return []

  // 缓存记录，避免重复计算
  const memo = new Array(n + 1).fill(null)

  const build = (n) => {
    const res = []

    if (n === 1) {
      res.push(new TreeNode(0))
      return res
    }

    // 缓存有就从缓存拿
    if (memo[n]) return memo[n]

    // 递归创建所有可能的真二叉树
    for (let i = 1; i < n; i += 2) {
      // 根节点占用1个节点，剩余节点需拆分为两个奇数i和j，满足i + j = n-1
      let j = n - i - 1

      // 递归获取所有可能的左右子树
      const leftSubTrees = build(i)
      const rightSubTrees = build(j)

      // 把所有可能的左右子树拼接起来拼接
      for (const left of leftSubTrees) {
        for (const right of rightSubTrees) {
          // 生成根节点
          const root = new TreeNode(0)
          // 拼接
          root.left = left
          root.right = right
          // 加入结果列表
          res.push(root)
        }
      }
    }

    // 设置缓存
    memo[n] = res

    return res
  }

  return build(n)
};